The present invention relates to programmable logic devices (PLDs), such as field-programmable gate arrays (FPGAs), and, more specifically, to computer-aided design (CAD) tools for such devices.
An FPGA is a programmable logic device having an array of configurable logic blocks (CLBs) connected together via a programmable routing structure. A typical FPGA may have tens of thousands of CLBs, each CLB having a plurality of primitive logic cells (or gates). Primitive cells of a CLB may be interconnected in a variety of ways to implement a desired logic function corresponding to that CLB.
FIGS. 1A-C illustrate a representative FPGA 100 comprising a plurality of CLBs 102 surrounded by input-output (I/O) blocks 104 and interconnected through a routing structure 106. CLBs 102 are typically connected to form a plurality of nets, one of which, net 108, is depicted in FIG. 1B. Illustratively, net 108 has ten CLBs 102 interconnected via routing structure 106 (not shown in FIG. 1B) as indicated by the solid lines. The physical dimensions of net 108 are characterized by a bounding box 110 shown by the dashed line in FIG. 1B. A different net may include a different number of CLBs 102 and/or I/O blocks 104. Each CLB 102 and/or I/O block 104 may belong to more than one net.
FIG. 1C shows schematically a representative structure of a configurable logic block. CLB 102 of FIG. 1C includes clusters 112-128. Each cluster has one or more primitive cells and is configured to implement a particular logic function/operation. For example, a cluster may be a look-up table (LUT), D-type flip-flop (DFF), multiplexer (MUX), carry chain, counter, multiplier, etc. Clusters within each CLB 102 may be interconnected in different ways to form one or more groups of clusters. A group may be defined as a set of one or more interconnected clusters in a CLB that are not connected to any other clusters in that CLB. Illustratively, clusters 112-116 are interconnected to form a first group 130 of clusters. Similarly, clusters 118-126 are interconnected to form a second group 132 of clusters. Cluster 128 is not connected to other clusters within CLB 102 and is referred to as an unrelated cluster (i.e., a single-cluster group). However, like all clusters, cluster 128 may be connected to one or more cells/clusters located in one or more different CLBs.
When an FPGA, such as FPGA 100 of FIG. 1, comprises thousands of CLBs in a large number of nets, the task of establishing the required multitude of interconnections between the CLBs in a net and between the different nets becomes so onerous that it requires CAD implementation. Accordingly, manufacturers of FPGAs including the assignee hereof, Lattice Semiconductor, Inc., develop place-and-route CAD tools to be used, e.g., by their customers (FPGA programmers) to implement their respective circuit designs. Typically, place-and-route software implements an iterative process aimed at producing a circuit configuration that meets certain customer specifications, such as insertion delays between specified pins and/or operation (clock) frequency. However, human intervention is often required to refine/finalize the CAD-optimized circuit configuration. Such intervention is relatively time-consuming and may result in longer time to market and higher product development costs.
The problems in the prior art are addressed in accordance with the principles of the present invention by a method for placing configurable logic blocks (CLBs) in a programmable logic device (PLD), such as a field-programmable gate array. In certain embodiments, after packing gates/clusters into blocks and then assigning those blocks to CLBs (e.g., using simulated annealing) to generate an initial placement for the PLD, the method changes the packing and/or placement of one or more CLBs prior to performing CLB routing. According to one embodiment, the K most critical paths in the initial placement are identified. For each node (e.g., a primitive cell or a cluster) of the most critical of the K paths (e.g., the path with the longest delay), moving the node to a different CLB located within a certain area adjacent to the current CLB is considered in order to reduce the criticality of that path. A move is applied if certain acceptability conditions are met. After the most critical path is improved, the rest of the identified paths are updated and the procedure is repeated for the new most critical of those K paths. In a preferred implementation, the present invention involves a combination of a net-based placement procedure, such as simulated annealing, with path-based node relocation. The method, which can be automated to reduce human intervention in the design process, improves circuit performance, e.g., by enabling higher circuit operation frequencies.
According to one embodiment, the present invention is a method of mapping a plurality of circuit elements onto a plurality of configurable logic blocks (CLBs) in a programmable logic device (PLD). According to the method, a mapping of the circuit elements to the CLBs in the PLD is generated, a critical path is selected in the PLD corresponding to the mapping, and, for at least one node of the critical path, node assignment is changed from a current location to a different location based on change of circuit performance corresponding to the change in node assignment.
According to another embodiment, the present invention is a circuit mapping generated by implementing the previously described method. According to yet another embodiment, the present invention is a machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements the previously described method.